home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cocktail
/
docme.lha
/
doc.me
/
highspeed.me
< prev
next >
Wrap
Text File
|
1992-09-25
|
39KB
|
1,293 lines
.\" use: pic | tbl | eqn | ditroff -me
.\"
.\" "@(#)bibmac.me 2.2 9/9/83";
.de IP
.ip \\$1 \\$2
..
.de LP
.lp
..
.\" @(#)bmac.std 2.2 9/9/83;
.\" standard format troff commands
.\" citation formatting strings
.ds [[ [
.ds ]] ]
.ds ], ,\|
.ds ]- -
.ds [. " \&
.ds .] .
.ds [, " \&
.ds ,] ,
.ds [? " \&
.ds ?] ?
.ds [: " \&
.ds :] :
.ds [; " \&
.ds ;] ;
.ds [! " \&
.ds !] !
.ds [" " \&
.ds "] \&"
.ds [' " \&
.ds '] '
.ds [< " \&
.ds >]
.\" reference formmating strings
.ds a] " \&
.ds b] , \&
.ds c] , \&
.ds n] "\& and \&
.ds m] "\& and \&
.ds p] .
.\" reference formmating macros
.de s[ \" start reference
.nh
.IP [\\*([F] 5m
..
.de e[ \" end reference
.[-
..
.de [] \" start to display collected references
.LP
..
.de ][ \" choose format
.ie !"\\*([J"" \{\
. ie !"\\*([V"" .nr t[ 1 \" journal
. el .nr t[ 5 \" conference paper
.\}
.el .ie !"\\*([B"" .nr t[ 3 \" article in book
.el .ie !"\\*([R"" .nr t[ 4 \" technical report
.el .ie !"\\*([I"" .nr t[ 2 \" book
.el .nr t[ 0 \" other
.\\n(t[[
..
.de 0[ \" other
.s[
.if !"\\*([A"" \\*([A\\c
.if !"\\*([T"" , \\*([T\\c
.if !"\\*([V"" , Vol. \\*([V\\c
.if !"\\*([O"" , \\*([O\\c
.if !"\\*([D"" , \\*([D\\c
\&.
.e[
..
.de 1[ \" journal article
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
\\fI\\*([J \\*([V\\fP\c
.if !"\\*([N"" ,\\*([N
.if !"\\*([D"" (\\*([D)\c
.if !"\\*([P"" , \\*([P\c
.if !"\\*([I"" , \\*([I\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de 2[ \" book
.s[
.ie !"\\*([A"" \\*([A,
.el .if !"\\*([E"" \{\
. ie \\n([E-1 \\*([E, eds.,
. el \\*([E, ed.,\}
.if !"\\*([T"" \\fI\\*([T\\fP,
.rm a[
.if !"\\*([I"" .ds a[ \\*([I
.if !"\\*([C"" \{\
. if !"\\*(a["" .as a[ , \\&
. as a[ \\*([C\}
.if !"\\*([D"" \{\
. if !"\\*(a["" .as a[ , \\&
. as a[ \\*([D\}
\\*(a[.
.if !"\\*([G"" Gov. ordering no. \\*([G.
.if !"\\*([O"" \\*([O.
.e[
..
.de 3[ \" article in book
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
in \\fI\\*([B\\fP\c
.if !"\\*([V"" , vol. \\*([V
.if !~\\*([E~~ \{\
. ie , \\n([E-1 \\*([E (editors)\c
. el , \\*([E (editor)\c\}
.if !"\\*([I"" , \\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" , \\*([D\c
.if !"\\*([P"" , \\*([P\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de 4[ \" report
.s[
.if !"\\*([A"" \\*([A,
.if !~\\*([E~~ \{\
. ie \\n([E-1 \\*([E, editors.
. el \\*([E, editor.\}
\\*([T,
\\*([R\c
.if !"\\*([G"" \& (\\*([G)\c
.if !"\\*([I"" , \\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" , \\*([D\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de 5[ \" conference paper
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
\\fI\\*([J\\fP,
.if !"\\*([C"" \\*([C,
.if !"\\*([D"" \\*([D\c
.if !"\\*([P"" , \\*([P\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de [- \" clean up after yourself
.rm [A [B [C [D
.rm [E [F [G
.rm [I [J [K
.rm [N [O [P
.rm [R [T
.rm [V [W
..
.\" @(#)bmac.std 2.2 8/24/83;
.\" standard format troff commands
.\" citation formatting strings
.ds [[ [
.ds ]] ]
.ds ], ,\|
.ds ]- -
.ds [. " \&
.ds .] .
.ds [, " \&
.ds ,] ,
.ds [< " \&
.ds >]
.\" reference formmating strings
.ds c] , \&
.ds n] "" and \&
.ds m] "" and \&
.ds a] " \&
.\" reference formmating macros
.de s[ \" start reference
.nh
.IP [\\*([F] 5m
..
.de e[ \" end reference
.[-
..
.de [] \" start to display collected references
.SH
References
.LP
..
.de ][ \" choose format
.ie !"\\*([J"" \{\
. ie !"\\*([V"" .nr t[ 1 \" journal
. el .nr t[ 5 \" conference paper
.\}
.el .ie !"\\*([B"" .nr t[ 3 \" article in book
.el .ie !"\\*([R"" .nr t[ 4 \" technical report
.el .ie !"\\*([I"" .nr t[ 2 \" book
.el .nr t[ 0 \" other
.\\n(t[[
..
.de 0[ \" other
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
.if !"\\*([O"" \\*([O\c
.if !"\\*([D"" , \\*([D\c
\&.
.e[
..
.de 1[ \" journal article
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
\\fI\\*([J \\*([V\\fP,
.if !"\\*([N"" \\*([N
.if !"\\*([D"" (\\*([D),
.if !"\\*([P"" \\*([P\c
.if !"\\*([I"" , \\*([I\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de 2[ \" book
.s[
.ie !"\\*([A"" \\*([A,
.el .if !"\\*([E"" \{\
. ie \\n([E-1 \\*([E, eds.,
. el \\*([E, ed.,\}
.if !"\\*([T"" \\fI\\*([T\\fP,
.rm a[
.if !"\\*([I"" .ds a[ \\*([I
.if !"\\*([C"" \{\
. if !"\\*(a["" .as a[ , \\&
. as a[ \\*([C\}
.if !"\\*([D"" \{\
. if !"\\*(a["" .as a[ , \\&
. as a[ \\*([D\}
\\*(a[.
.if !"\\*([G"" Gov. ordering no. \\*([G.
.if !"\\*([O"" \\*([O.
.e[
..
.de 3[ \" article in book
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
in \\fI\\*([B\\fP,
.if !"\\*([V"" vol. \\*([V,
.if !"\\*([E"" \\*([E (ed.),
.if !"\\*([I"" \\*([I,
.if !"\\*([C"" \\*([C,
.if !"\\*([D"" \\*([D\c
.if !"\\*([P"" , \\*([P\c
\\&.
.if !"\\*([O"" \\*([O.
.e[
..
.de 4[ \" report
.s[
.if !"\\*([A"" \\*([A,
\\*([T,
\\*([R\c
.if !"\\*([G"" \& (\\*([G)\c
.if !"\\*([I"" , \\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" , \\*([D\c
\\&.
.if !"\\*([O"" , \\*([O.
.e[
..
.de 5[ \" conference paper
.s[
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([T,
\\fI\\*([J\\fP,
.if !"\\*([C"" \\*([C\c
.if !"\\*([D"" , \\*([D\c
.if !"\\*([P"" , \\*([P\c
\\&.
.if !"\\*([O"" , \\*([O.
.e[
..
.de [- \" clean up after yourself
.rm [A [B [C [D
.rm [E [F [G
.rm [I [J [K
.rm [N [O [P
.rm [R [T
.rm [V [W
..
.if t \{ \
.pl 29.7c \" page length
.po 2.5c \" page offset (left margin)
.ll 16.5c \" line length
.lt 16.5c \" title length
.nr LL 16.5c
.nr )l 29.7c
.nr hm 2c
.nr $r 9 \" factor for vertical spacing
.nr $R \n($r
.sz 12 \" font size
.nr pp 12
.nr sp 12
.nr tp 12
.nr fp 10
.hc ~ \" hyphenation character
. \" Umlauts and sharp s
.ds A \(A:
.ds O \(O:
.ds U \(U:
.ds a \(a:
.ds o \(o:
.ds u \(u:
.ds s \(ss
. \" UMLAUT \*:u, etc.
.ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
.\}
.if n \{ \
.po 0 \" page offset (left margin)
.ll 78 \" line length
.lt 78 \" title length
.nr $r 4 \" factor for vertical spacing
.nr $R \n($r
.hc ~ \" hyphenation character
. \" Umlaute und scharfes s
.ds A Ae
.ds O Oe
.ds U Ue
.ds a ae
.ds o oe
.ds u ue
.ds s sz
.\}
.de _
\&\\$1\l'|0\(ul'\\$2
..
.de FT \" font for programs
.ft C
.sz -2
..
.de FR
.ft R
.sz +2
..
.de [] \" start to display collected references
.uh References
.lp
..
.de $0 \" collect table of contents
.(x
.ta 2c
.ie '\\$2'' \\$1
.el \\$2. \\$1
.)x
..
.de np
.nr $p +1
.ip \\n($p.
..
.de SH
.sp 0.5
.in -3
.r \\$1
.sp 0.5
.in +3
..
.de PP
.sp 0.5
..
.de IP
.ip \\$1 \\$2
..
.de I
.i \\$1
..
.de TH
..
.hc @
.EQ
delim off
.EN
.de FR
.ft R
.sz +2
..
.b " "
.sp 1c
.ta 9c
.ft R
.sz 12
\l'17.1c'
.nf
Generators for
High-Speed Front-Ends
J. Grosch
\l'17.1c'
.sp 12.5c
\l'17.1c'
.ft H
.nf
GESELLSCHAFT F\*UR MATHEMATIK
UND DATENVERARBEITUNG MBH
FORSCHUNGSSTELLE F\*UR
PROGRAMMSTRUKTUREN
AN DER UNIVERSIT\*AT KARLSRUHE
.r
\l'17.1c'
.bp
.oh '''%'
.eh '''%'
.ce 99
.sz 20
.b " "
.sp 2
Project
.sp
.b "Compiler Generation"
.sp
.sz 12
\l'15c'
.sp
.sz 16
.b "Generators for High-Speed Front-Ends"
.sp 2
Josef Grosch
.sp 2
.sz 14
Sept. 28, 1988
.sp
.sz 12
\l'15c'
.sp 2
Report No. 11
.sp 2
Copyright \(co 1988 GMD
.sp 2
Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
Forschungsstelle an der Universit\*at Karlsruhe
Vincenz-Prie\*snitz-Str. 1
D-7500 Karlsruhe
.ce 0
.fi
.bp 2
.ce 99
.b
Generators for High-Speed Front-Ends
.sp 2
.r
Josef Grosch
GMD Forschungsstelle f\*ur Programmstrukturen an der Universit\*at Karlsruhe
Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe 1, West Germany
.sp 2
.ce 0
.uh Abstract
.pp
High-speed compilers can be constructed automatically. We present some
existing tools for the generation of fast front-ends.
.\" High-speed compilers can be constructed automatically. We present some
.\" existing tools for the generation of front-ends and describe our current
.\" work on future tools.
.pp
.i Rex
(Regular EXpression tool) is a scanner generator whose specifications are
based on regular expressions and arbitrary semantic actions written in one
of the target languages C or Modula-2. As scanners sometimes have to
consider the context to unambiguously recognize a token the right context
can be specified by an additional regular expression and the left context
can be handled by so-called start states. The generated scanners
automatically compute the line and column position of the tokens and offer
an efficient mechanism to normalize identifiers and keywords to upper or
lower case letters. The scanners are table-driven and run at a speed of
180,000 to 195,000 lines per minute on a MC 68020 processor.
.pp
.i Lalr
is a LALR(1) parser generator accepting grammars written in extended BNF
notation which may be augmented by semantic actions expressed by statements
of the target language. The generator provides a mechanism for
S-attribution, that is synthesized attributes can be computed during
parsing. In case of LR-conflicts, unlike other tools,
.i Lalr
provides not only information about an internal state consisting of a set of
items but it prints a derivation tree which is much more useful to analyze
the problem. Conflicts can be resolved by specifying precedence and
associativity of operators and productions. The generated parsers include
automatic error reporting, error recovery, and error repair. The parsers are
table-driven and run at a speed of 580,000 lines per minute. Currently
parsers can be generated in the target languages C and Modula-2.
.pp
.i Ell
is a LL(1) parser generator accepting the same specification language as
.i Lalr
except that the grammars must obey the LL(1) property. The generated parsers
include automatic error reporting, recovery, and repair like
\fILalr\fP.
The parsers are implemented following the recursive descent method and reach
a speed of 900,000 lines per minute. The possible target languages are again
C and Modula-2.
.pp
A comparison of the above tools with the corresponding UNIX tools shows
that significant improvements have been achieved thus allowing
the generation of high-speed compilers.
.\" .pp
.\" Currently we are working on tools for semantic analysis and transformation.
.\" Semantic analysis will be based on attribute grammars. We are trying to
.\" structure semantic analysis into separate, probably reusable modules and to
.\" combine this with an efficient way to perform attribute evaluation. The
.\" transformation phase maps an attributed tree to an intermediate
.\" language. This phase can be specified by a tree mapping and it can be
.\" implemented efficiently based on pattern matching.
.sh 1 "The Scanner Generator Rex"
.pp
The scanner generator \fIRex\fP has been developed with the aim to combine
the powerful specification method of regular expressions with the generation
of highly efficient scanners. The name \fIRex\fP stands for
.i "regular expression tool,"
reflecting the specification method.
.pp
A scanner specification consists in principle of a set of regular
expressions each associated with a semantic action. Whenever a string
constructed according to a regular expression is recognized in the input of
the scanner its semantic action which is a sequence of arbitrary statements
written in the target language is executed. To be able to recognize tokens
depending on their context \fIRex\fP provides start states to handle left context
and the right context can be specified by an additional regular expression.
If several regular expressions match the input characters, the
longest match is preferred. If there are still several possibilities, the
regular expression given first in the specification is chosen.
.pp
\fIRex\fP generated scanners automatically provide the line and column position of
each token. For languages like Pascal and Ada where the case of letters is
insignificant tokens can be normalized to lower or upper case. There are
predefined rules to skip white space like blanks, tabs, or newlines.
.pp
The generated scanners are table-driven deterministic finite automatons. The
tables are compressed using the so-called comb-vector technique
\*([[ASU86\*(]]. Whereas the generator \fIRex\fP is implemented in Modula-2
it can generate scanners in the languages C and Modula-2. Currently \fIRex\fP is
available for PCS Cadmus/UNIX and SUN/UNIX workstations.
.pp
The most outstanding feature of \fIRex\fP is its speed. The generated scanners
process nearly 200,000 lines per minute without hashing of identifiers and
up to 150,000 lines per minute if hashing is applied. This is 4 times the
speed of \fILex\fP\*([<\*([[Les75\*(]]\*(>] generated scanners. In typical cases \fIRex\fP generated
scanners are 4 times smaller then \fILex\fP generated ones (around 15 KB). Usually
\fIRex\fP takes only 1/10 of the time of \fILex\fP to generate a scanner. All figures
have been measured on a MC 68020 processor.
.pp
In the following we will demonstrate the powerful specification method
provided by \fIRex\fP and present a comparison with other scanner generators.
.sh 2 "Structure of Specification"
.(z I
.FT
EXPORT { external declarations }
GLOBAL { global declarations }
LOCAL { local declarations }
BEGIN { initialization code }
CLOSE { finalization code }
DEFAULT { default action }
EOF { end of file action }
DEFINE definition of regular expressions
START definition of start states
RULE regular expressions and semantic actions
.FR
Fig. 1: Structure of Specification
.)z
.pp
A complete scanner specification is structured like shown in Figure 1. The
regular expressions may be preceded by six sections containing arbitrary
target code, which may contain declarations to be used in the semantic
actions or statements for initialization and finalization of data
structures. The DEFINE and START sections serve to abbreviate regular
expressions by identifiers and to declare start states (see below).
A complete definition of the specification language can be found in the user
manual\*([<\*([[Gro87\*(]]\*(>].
.sh 2 "Right Context"
.pp
There are languages where the strategy of the longest match fails. For
example in Modula-2 the input \fC1..\fP has to be recognized as
tokens "\fC1\fP" and "\fP..\fP", not as "\fC1.\fP" and "\fP.\fP",
which are also two legal Modula tokens.
The problem can be solved using an additional regular expression to describe
this situation where the right context of a token leads to an exception in
the longest match strategy. Figure 2 shows the syntax used in \fIRex\fP for
regular expressions and semantic actions to describe the 4 tokens involved
in the above problem. The character '/' separating two regular expressions
specifies to recognize a sequence of digits only if it is followed
by two dots.
.(b I
.sp 0.5
.FT
{0-9} + : { return SymDecimal; }
{0-9} + / ".." : { return SymDecimal; }
{0-9} + "." {0-9} * : { return SymReal ; }
".." : { return SymRange ; }
"." : { return SymDot ; }
.FR
Fig. 2: Scanner Specification Using Right Context
.)b
.sh 2 "Start States"
.(z I
.FT
GLOBAL {VAR NestingLevel: CARDINAL;}
.sp 0.5
BEGIN {NestingLevel := 0;}
.sp 0.5
EOF {IF yyStartState = Comment THEN Error ("unclosed comment"); END;}
.sp 0.5
DEFINE CmtCh = - {*(\\\\t\\\\n}.
.sp 0.5
START Comment
.sp 0.5
RULES
"(*" : {INC (NestingLevel); yyStart (Comment);}
.sp 0.5
#Comment# "*)" : {DEC (NestingLevel);
IF NestingLevel = 0 THEN yyStart (STD); END;}
.sp 0.5
#Comment# "(" | "*" | CmtCh + : {}
.FR
Fig. 3: Scanner Specification Using Start States
.)z
.pp
To handle tokens whose recognition depends on the left context or to process
even tokens which cannot be specified by regular expressions the scanners
can have several start states. In every start state a different set of
regular expressions is recognized. There is a special statement to change
the current start state (yyStart). For example nested comments like in
Modula can be scanned as shown in Figure 3.
.sh 2 "Ada Quote Problem"
.pp
The Ada quote problem can also be solved using start states. The problem is
to scan for example
.(b
.FT
t'(',',',',',') \fP as \fP
t ' ( ',' , ',' , ',' ) \fP and not as \fP
t '(' , ',' , ',' , ' )
.)b
which are both possible sequences of Ada tokens. The correct solution again
violates the longest match strategy. A careful study of the language
definition reveals that single quotes only appear behind identifiers and
closing parentheses. Figure 4 shows the structure of a solution.
After recognizing one of these two tokens we switch to start state QUOTE
which recognizes among other tokens single quotes. After all the other
tokens we switch to the predefined start state STD where quotes are only
accepted as delimiters for character literals.
More examples of scanner specifications can be found in\*([<\*([[Gro88\*(]]\*(>].
.(b I
.sp 0.5
.FT
.\" EXPORT {
.\" # include "SymbolTable.h"
.\" typedef union {char vChar; tSymbol vSymbol} tAttribute;
.\" extern void ErrorAttribute (); }
.\"
.\" GLOBAL {
.\" void ErrorAttribute (Symbol, Attribute) ... }
.\"
LOCAL {char Word [256]; int L;}
.sp 0.5
DEFINE character = {\\\\ -~}.
letter = {A-Z a-z}.
digit = {0-9}.
.sp 0.5
START QUOTE
.sp 0.5
RULES
.sp 0.5
#STD# ' character ' : {
L = GetWord (Word);
Attribute.vChar = Word [1];
return SymCharacterLiteral;}
.sp 0.5
#QUOTE# ' : {
yyStart (STD);
return SymApostrophe;}
.sp 0.5
"(" : {yyStart (STD); return SymLParenthesis;}
.sp 0.5
")" : {yyStart (QUOTE); return SymRParenthesis;}
.sp 0.5
letter (_? (letter | digit)+ )* : {
yyStart (QUOTE); L = GetLower (Word);
Attribute.vSymbol = MakeSymbol (Word, L);
return SymIdentifier;}
.FR
Fig. 4: Scanner Specification Solving the Ada Quote Problem
.)b
.sh 2 "Comparison of Scanner Generators"
.(z
.TS
tab (;) box center;
l | l l l
l | l l l.
;Lex ;Flex ;Rex
_
specification ;regular;regular;regular
language ; expressions; expressions; expressions
semantic actions ;yes ;yes ;yes
right context ;yes ;yes ;yes
start states ;yes ;yes ;yes
_
conflict solution ;longest match;longest match;longest match
;first rule ;first rule ;first rule
_
source coordinates;line ;- ;line + column
case normalization;- ;yes ;yes
predefined rules to;- ;- ;yes
skip white space
several solutions ;yes ;yes ;-
(REJECT)
adjustment of ;by hand;automatic;automatic
internal arrays
_
scanning method ;table-driven ;table-driven ;table-driven
table compression ;comb-vector ;comb-vector ;comb-vector
_
implementation ;C ;C ;C, Modula
languages
target languages ;C ;C ;C, Modula
_
speed [lines/min.]
without hashing;36,400 ;139,000;182,700
with hashing ;34,700 ;118,000;141,400
_
table size [bytes];39,200 ;57,300 ;4,400
scanner size [bytes];43,800 ;64,100 ;11,200
_
generation time [sec.];73.7;7.2 ;4.9
.TE
.ce
Fig. 5: Comparison of Scanner Generators (speed measured on MC 68020 processor)
.)z
.pp
Figure 5 compares \fIRex\fP to the classical UNIX scanner generator \fILex\fP\*([<\*([[Les75\*(]]\*(>]
and to the new public domain remake of \fILex\fP called \fIFlex\fP\*([<\*([[Pax88\*(]]\*(>]
(for fast \fILex\fP). The table
compares the specification technique and the performance of the generators
as well as of the generated scanners. The specification dependent numbers
for generation time and scanner size are for a Modula-2 scanner.
.sh 1 "The Parser Generator Lalr"
.pp
The parser generator \fILalr\fP has been developed with the aim to combine a
powerful specification technique for context-free languages with the
generation of highly efficient parsers. As it processes the class of LALR(1)
grammars we chose the name \fILalr\fP to express the power of the specification
technique.
.pp
The grammars may be written using extended BNF constructs. Each grammar rule
may be associated with a semantic action consisting of arbitrary statements
written in the target language. Whenever a grammar rule is recognized by the
generated parser the associated semantic action is executed. A mechanism for
S-attribution (only synthesized attributes) is provided to allow
communication between the semantic actions.
.pp
In case of LR-conflicts a derivation tree is printed to ease in locating the
problem. The conflict can be resolved by specifying precedence and
associativity for terminals and rules. Syntactic errors are handled fully
automatically by the generated parsers including error reporting, recovery,
and repair. The mentioned features are discussed in more detail in the
following chapters.
.pp
The generated parsers are table-driven. Like in the case of \fIRex\fP comb-vector
technique is used to compress the parse tables. The generator \fILalr\fP is
implemented in the language Modula-2. Parsers can be generated in the
languages C and Modula-2. The generator uses the algorithm described by
\*([[DeP82\*(]] to compute the look-ahead sets although the
algorithm published by\*([<\*([[Ive86\*(]]\*(>] promises to perform better. Currently \fILalr\fP is
available for PCS-Cadmus/UNIX and SUN/UNIX workstations.
.pp
Parsers generated by \fILalr\fP are twice as fast as \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>] generated
ones. They reach a speed of 580,000 lines per minute on a MC 68020 processor
excluding the time for scanning. The size of the parsers is only slightly
increased in comparison to \fIYacc\fP (e. g. 37 KB for Ada), because there
is a small price to be paid for the speed.
.pp
In the following we will discuss some features of \fILalr\fP in detail and
present a comparison to other parser generators.
Further information about the implementation
of \fILalr\fP can be found in\*([<\*([[Gro90\*(]]\*(>].
.sh 2 "Structure of Specification"
.(z I
.FT
EXPORT { external declarations }
GLOBAL { global declarations }
LOCAL { local declarations }
BEGIN { initialization code }
CLOSE { finalization code }
TOKEN coding of terminals
OPER precedence of operators
RULE grammar rules and semantic actions
.FR
Fig. 6: Structure of Specification
.)z
.pp
The structure of a parser specification follows the style of a \fIRex\fP
specification as shown in Figure 6. Again, there may be five sections to
include target code. The TOKEN section defines the terminals of the grammar
and their encoding. In the OPER (for operator) section precedence and
associativity for terminals can be specified to resolve LR-conflicts. The
RULE section contains the grammar rules and semantic actions.
A complete definition of the specification language can be found in the user
manual\*([<\*([[GrV88\*(]]\*(>].
.sh 2 "S-Attribution"
.pp
Figure 7 shows an example for the syntax of grammar rules and semantic
actions. The semantic actions may access and evaluate attributes associated
with the nonterminals and terminals of the grammar rules. This attributes
are currently denoted in the less readable "numeric" style of \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>].
.(b I
.sp 0.5
.FT
expr : expr '+' expr { $0.value := $1.value + $3.value; } .
expr : expr '*' expr { $0.value := $1.value * $3.value; } .
expr : '(' expr ')' { $0.value := $2.value; } .
expr : number { $0.value := $1.value; } .
.FR
Fig. 7: Grammar Rules Using S-Attribution
.)b
.sh 2 "Ambiguous Grammars"
.pp
The grammar of Figure 7 as well as the example in Figure 8 are typical
examples of ambiguous grammars. Like \fIYacc\fP we allow to resolve the resulting
LR-conflicts
by specifying precedence and associativity for terminals in the OPER
section. Figure 9 gives an example. The lines represent increasing levels of
precedence. LEFT, RIGHT, and NONE denote left-associativity,
right-associativity, and no associativity. Rules can inherit the properties
of a terminal with the PREC suffix.
.(b I
.sp 0.5
.FT
stmt : 'IF' expr 'THEN' stmt PREC LOW
| 'IF' expr 'THEN' stmt 'ELSE' stmt PREC HIGH .
.FR
Fig. 8: Ambiguous Grammar (Dangling Else)
.)b
.(b I
.FT
OPER LEFT '+'
LEFT '*'
NONE LOW
NONE HIGH
.FR
Fig. 9: Resolution of LR-Conflicts Using Precedence and Associativity
.)b
.sh 2 "LR-Conflict Message"
.(z I
.FT
State 266
read reduce conflict
\&program End-of-Tokens
\&'PROGRAM' identifier params ';' block '.'
\&................................:
\&:
\&labels consts types vars procs 'BEGIN' stmts 'END'
\&.......................................:
\&:
\&stmt
\&'IF' expr 'THEN' stmt 'ELSE' stmt
:
'IF' expr 'THEN' stmt
:
reduce stmt -> 'IF' expr 'THEN' stmt. {'ELSE'} ?
read stmt -> 'IF' expr 'THEN' stmt.'ELSE' stmt ?
.FR
Fig. 10: Derivation Tree for an LR-Conflict (Dangling Else)
.)z
.pp
To ease in locating the reason for LR-conflicts we adopted the method
proposed by\*([<\*([[DeP82\*(]]\*(>]. Besides reporting the type of
the conflict and the involved items (whatever that is for the user) like most
LR parser generators do, additionally a derivation tree is printed.
Figure 10 shows an
example. It shows how the items and the look-ahead tokens get into the
conflict situation. In general there can be two trees if the derivations for
the conflicting items are different. Each tree consists of 3 parts. An
initial part begins at the start symbol of the grammar. At a certain node
(rule) two subtrees explain the emergence of the item and the look-ahead.
.pp
Every line contains a right-hand side of a grammar rule. Usually the
right-hand side is indented to start below the nonterminal of the left-hand
side. To avoid line overflow dotted edges also refer to the left-hand side
nonterminal and allow to shift back to the left margin. In Figure 10 the
initial tree part consists of 5 lines (not counting the dotted lines). The
symbols 'stmt' and 'ELSE' are the roots of the other two tree parts. This
location is indicated by the "unnecessary" colon in the following line.
After one intermediate line the left subtree derives the conflicting items.
The right subtree consists in this case only of the root node (the terminal
\&'ELSE') indicating the look-ahead. In general this can be a tree of
arbitrary size. The LR-conflict can easily be seen from this tree fragment.
If conditional statements are nested like shown there is a read reduce
conflict (also called shift reduce conflict).
.sh 2 "Error Recovery"
.(z I
Source Program:
.sp 0.5
.FT
program test (output);
begin
if (a = b] write (a);
end.
.sp 0.5
.FR
Error Messages:
.sp 0.5
.FT
3, 13: Error syntax error
3, 13: Information expected symbols: ')' '*' '+' '-' '/' '<' '<='
'=' '<>' '>' '>=' 'AND' 'DIV' 'IN' 'MOD' 'OR'
3, 15: Information restart point
3, 15: Repair symbol inserted : ')'
3, 15: Repair symbol inserted : 'THEN'
.FR
Fig. 11: Example of Automatic Error Messages
.)z
.pp
The generated parsers include information and algorithms to handle syntax
errors completely automatically. We follow the complete backtrack-free
method described by
\*([[R\*oh76\*(],R\*oh80\*(],R\*oh82\*(]]
and provide expressive reporting, recovery, and repair. Every incorrect input
is "virtually" transformed into a syntactically correct program with the
consequence of only executing a "correct" sequence of semantic actions.
Therefore the following compiler phases like semantic analysis don't have to
bother with syntax errors. \fILalr\fP provides a prototype error module which
prints messages as shown in Figure 11.
Internally the error recovery works as follows:
.ip - 0.5c
The location of the syntax error is reported.
.ip - 0.5c
All the tokens that would be a legal continuation of the program are
computed and reported.
.ip - 0.5c
All the tokens that can serve to continue parsing are computed. A minimal
sequence of tokens is skipped until one of these tokens is found.
.ip - 0.5c
The recovery location is reported.
.ip - 0.5c
Parsing continues in the so-called repair mode. In this mode the parser
behaves as usual except that no tokens are read from the input. Instead a
minimal sequence of tokens is synthesized to repair the error.
The parser stays in this mode until the input token can be accepted.
The synthesized tokens are reported. The program can be regarded as
repaired, if the skipped tokens are replaced by the synthesized ones.
With leaving the repair mode parsing continues as usual.
.sh 2 "Comparison of Parser Generators"
.(z
.TS
tab (;) box center;
l1 |1 l1 l1 l1 l1 l
l1 |1 l1 l1 l1 l1 l.
;Bison ;Yacc ;PGS ;Lalr ;Ell
_
spec. language ;BNF ;BNF ;EBNF ;EBNF ;EBNF
grammar class ;LALR(1);LALR(1);LALR(1);LALR(1);LL(1)
; ; ;LR(1) ; ;
; ; ;SLR(1) ; ;
semantic actions ;yes ;yes ;yes ;yes ;yes
S-attribution ;numeric;numeric;symbolic;numeric;-
L-attribution ;- ;- ;- ;- ;planned
_
conflict message ;state, ;state, ;state, ;derivation-;-
; items; items; items; tree ;
conflict solution;precedence;precedence;modification;precedence;
;associativity;associativity; ;associativity;
chain rule elim. ;- ;- ;yes ;- ;-
error recovery ;by hand;by hand;automatic;automatic;automatic
error repair ;- ;- ;yes ;yes ;yes
_
parsing method ;table-driven;table-driven;table-driven;table-driven;recursive
; ; ; ; ; descent
table compression;comb-vector;comb-vector;comb-vector;comb-vector;-
_
impl. language ;C ;C ;Pascal ;Modula ; Modula
target languages ;C ;C ;C ;C ;C
; ; ;Modula ;Modula ;Modula
; ; ;Pascal
; ; ;Ada
_
speed [tokens/sec.];9,000;16,000;17,300;35,000;54,600
speed [lines/min.];150,000;270,000;290,000;580,000;900,000
_
table size [bytes] ;8,004;10,364 ;11,268 ;11,795 ;-
parser size [bytes];11,136;12,548 ;17,616 ;17,416 ;14,344
_
gen. time [sec.] ;5.0 ;19.6 ;69.5 ;29.6 ;6.4
_
availability ;UNIX ;UNIX ;PCS/UNIX;PCS/UNIX;PCS/UNIX
; ; ;VAX/UNIX;SUN/UNIX;SUN/UNIX
; ; ; BSD 4.2
; ; ;SIEMENS/
; ; ; BS2000
.TE
.ce
Fig. 12: Comparison of Parser Generators (speed measured on a MC 68020 processor)
.)z
.pp
Figure 12 compares \fILalr\fP with:
.ta 1.5c
.ip - 0.5c
Yacc well known from UNIX\*([<\*([[Joh75\*(]]\*(>]
.ip - 0.5c
Bison public domain remake of \fIYacc\fP\*([<\*([[GNU88\*(]]\*(>]
.ip - 0.5c
PGS Parser Generating System also developed at Karlsruhe\*([<\*([[GrK86\*(],KlM89\*(]]\*(>]
.ip - 0.5c
Ell recursive descent parser generator described in chapter 3.
.pp
The language dependent numbers exclude time and size for scanning and refer
to experiments with a Modula-2 parser.
.pp
The measurements of the parser speed turned out to be a hairy business.
The results can be influenced in many ways from:
.ip - 0.5c
The hardware: We used a PCS Cadmus 9900 with a MC68020 processor running
at a clock rate of 20 MHz.
.ip - 0.5c
The compiler: We used the C compiler of PCS.
.ip - 0.5c
The language: We used Modula-2.
.ip - 0.5c
The size of the language: In the case of \fILalr\fP the size of the
language or the size of the grammar does not influence the speed of the
parser because the same table-driven algorithm and the same data structure
is used in every case. This can be different for other parsers. For example
the speed of directly coded parsers decreases with an increasing grammar
size. PGS stores states in one byte if there are less than 256 states and in
two bytes otherwise. This increases the speed for small grammars, too,
at least on byte-addressable machines.
.ip - 0.5c
The grammar style, the number of rules, especially chain rules and the
like: We used the same grammar for most experiments which had as few chain
rules as possible and which caused as few reduce actions as possible. This
means e. g. we specified expressions in an ambiguous style like shown in
Figure 7. Exceptions are \fIEll\fP which needs an LL(1) grammar and PGS, because
modifications are inelegant to resolve many ambiguities.
.ip - 0.5c
The test input: We used the same large Modula program as test data in
every case, of course.
Nevertheless the programming style or the code "density" influence the
resulting speed. This effect could be eliminated by selecting tokens per
minute as measure. In spite of this we chose lines per minute as measure
because we find this to be more expressive.
(In the average there are 4 tokens in a line).
.ip - 0.5c
The timing: We measured CPU-time and subtracted the total time and the
scanner time to get the parser time.
.ip - 0.5c
The semantic actions: We specified empty semantic actions for all rules in
order to simulate the conditions in a realistic application. This has more
consequences as one might think. It disables a short cut of \fIYacc\fP and the
chain rule elimination\*([<\*([[WaG84\*(]]\*(>] of PGS,
decreasing the speed in both cases. A further
experiment with PGS revealed even more problems. To allow chain rule
elimination we deleted the empty semantic actions for chain rules.
Surprisingly, instead of getting faster the parser was slower. The reason is
that chain rule elimination increases the number of states. Accidentally we
exceeded the number of 256. Now states have to be stored in two bytes instead
of one. The additional memory accesses are more expensive than the win from
the chain rule elimination.
.sh 1 "The Parser Generator Ell"
.pp
The parser generator \fIEll\fP processes LL(1) grammars which may contain extended
BNF constructs and semantic actions and generates a recursive descent
parser. A mechanism for L-attribution (inherited and synthesized attributes
evaluable during one preorder traversal) is to be added. Like \fILalr\fP syntax
errors are handled fully automatic including error reporting from a prototype
error module, error recovery, and error repair. The generator \fIEll\fP is
implemented in Modula-2 and can generate parsers in C and Modula-2. Those
satisfied with the restricted power of LL(1) grammars may profit from the
high speed of the generated parsers which lies around 900,000 lines per
minute. For a detailed comparison see Figure 12.
.sh 1 "Conclusion"
.pp
We presented the tools \fIRex\fP, \fILalr\fP, and \fIEll\fP that allow the
generation of
efficient compiler front-ends. The combination of generated scanners and
parsers reach speeds of more than 100,000 lines per minute or almost
2,000 lines per second. As scanning itself is one of the dominating tasks in
a compiler we belief that compilers with a total performance of 1,000 lines
per second can be generated automatically. Our current work concentrates on
tools for semantic analysis based on attribute grammars and code generation
based on pattern matching.
.uh Acknowledgements
.pp
The author implemented \fIRex\fP and contributed the parser skeletons in C
and Modula-2 for \fILalr\fP. The generator program \fILalr\fP was written
and debugged by Bertram Vielsack who also
provided the experimental results for the parser generators.
The parser generator \fIEll\fP was programmed by Doris Kuske.
.fi
.sz 12
.[]
.[-
.ds [F ASU86
.ds [A A\*(p]\*(a]V\*(p] Aho
.as [A \*(c]R\*(p] Sethi
.as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
.ds [T Compilers: Principles, Techniques, and Tools
.ds [I Addison Wesley
.ds [C Reading, M\&A
.ds [D 1986
.][
.[-
.ds [F DeP82
.ds [A F\*(p] DeRemer
.as [A \*(n]T\*(p] Pennello
.ds [T Efficient Computation of LALR(1) Look-Ahead Sets
.nr [P 1
.ds [P 615-649
.ds [J ACM Trans. Prog. Lang. and Systems
.ds [V 4
.ds [N 4
.ds [D Oct. 1982
.][
.[-
.ds [F GNU88
.ds [A GNU\ Project
.ds [T Bison - Manual Page
.ds [I Public Domain Software
.ds [D 1988
.][
.[-
.ds [F GrK86
.ds [A J\*(p] Grosch
.as [A \*(n]E\*(p] Klein
.ds [T User Manual for the PGS-System
.ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
.ds [D Aug. 1986
.][
.[-
.ds [F Gro87
.ds [A J\*(p] Grosch
.ds [T Rex - A Scanner Generator
.ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
.ds [R Compiler Generation Report No. 5
.ds [N 5
.ds [D Dec. 1987
.][
.[-
.ds [F Gro88
.ds [A J\*(p] Grosch
.ds [T Selected Examples of Scanner Specifications
.ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
.ds [R Compiler Generation Report No. 7
.ds [N 7
.ds [D Mar. 1988
.][
.[-
.ds [F GrV88
.ds [A J\*(p] Grosch
.as [A \*(n]B\*(p] Vielsack
.ds [T The Parser Generators Lalr and Ell
.ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
.ds [R Compiler Generation Report No. 8
.ds [N 8
.ds [D Apr. 1988
.][
.[-
.ds [F Gro90
.ds [A J\*(p] Grosch
.ds [T Lalr - a Generator for Efficient Parsers
.ds [J Software\(emPractice & Experience
.ds [V 20
.ds [N 11
.ds [D Nov. 1990
.nr [P 1
.ds [P 1115-1135
.][
.[-
.ds [F Ive86
.ds [A F\*(p] Ives
.ds [T Unifying View of Recent LALR(1) Lookahead Set Algorithms
.ds [J SI\&GPLAN Notices
.ds [V 21
.ds [N 7
.nr [P 1
.ds [P 131-135
.ds [D 1986
.][
.[-
.ds [F Joh75
.ds [A S\*(p]\*(a]C\*(p] Johnson
.ds [T Yacc \(em Yet Another Compiler-Compiler
.ds [R Computer Science Technical Report 32
.ds [I Bell Telephone Laboratories
.ds [C Murray Hill, NJ
.ds [D July 1975
.][
.[-
.ds [F KlM89
.ds [A E\*(p] Klein
.as [A \*(n]M\*(p] Martin
.ds [T The Parser Generating System PGS
.ds [J Software\(emPractice & Experience
.ds [V 19
.ds [N 11
.nr [P 1
.ds [P 1015-1028
.ds [D Nov. 1989
.][
.[-
.ds [F Les75
.ds [A M\*(p]\*(a]E\*(p] Lesk
.ds [T LEX \(em A Lexical Analyzer Generator
.ds [R Computing Science Technical Report 39
.ds [I Bell Telephone Laboratories
.ds [C Murray Hill, NJ
.ds [D 1975
.][
.[-
.ds [F Pax88
.ds [A V\*(p] Paxson
.ds [T Flex - Manual Pages
.ds [I Public Domain Software
.ds [D 1988
.][
.[-
.ds [F R\*oh76
.ds [A J\*(p] R\\*:ohrich
.ds [T Syntax-Error Recovery in LR-Parsers
.ds [E H\*(p] Schneider
.ds [E H.-J\*(p] Schneider
.as [E \*(n]M\*(p] Nagl
.nr [E 2
.ds [S Programmiersprachen, 4. Fachtagung der GI, Erlangen
.ds [B Informatik-Fachberichte
.ds [V 1
.nr [P 1
.ds [P 175-184
.ds [C Berlin
.ds [I Springer Verlag
.ds [D 1976
.][
.[-
.ds [F R\*oh80
.ds [A J\*(p] R\\*:ohrich
.ds [T Methods for the Automatic Construction of Error Correcting Parsers
.ds [J Acta Inf.
.ds [V 13
.ds [N 2
.nr [P 1
.ds [P 115-139
.ds [D 1980
.][
.[-
.ds [F R\*oh82
.ds [A J\*(p] R\\*:ohrich
.ds [T Behandlung syntaktischer Fehler
.ds [J Informatik Spektrum
.ds [V 5
.ds [N 3
.nr [P 1
.ds [P 171-184
.ds [D 1982
.][
.[-
.ds [F WaG84
.ds [A W\*(p]\*(a]M\*(p] Waite
.as [A \*(n]G\*(p] Goos
.ds [T Compiler Construction
.ds [I Springer Verlag
.ds [C New York, NY
.ds [D 1984
.][
.bp 1
.lp
.b Contents
.sp
.xp